public class Solution540 {
    public int singleNonDuplicate(int[] nums) {
        int l=0,r=nums.length-1;
        while (l<=r){
            int mid=(l+r)/2;
            if (l==r || nums[mid]!=nums[mid-1] && nums[mid]!=nums[mid+1]){
                return nums[mid];
            }
            if ((mid-l)%2==0 && nums[mid]==nums[mid+1]){
                l=mid+2;
            }else if ((mid-l)%2==0 && nums[mid]==nums[mid-1]){
                r=mid-2;
            }else if ((mid-l)%2==1 && nums[mid]==nums[mid+1]){
                r=mid-1;
            }else{
                l=mid+1;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        System.out.println(new Solution540().singleNonDuplicate(new int[]{1,1,2,2,3}));
    }
}
